\n \n \n
\n
\n\n \n \n Dinneen, M. J.; Ventura, J. A.; Wilson, M. C.; and Zakeri, G.\n\n\n \n \n \n \n \n Construction of time-relaxed minimal broadcast networks.\n \n \n \n \n\n\n \n\n\n\n
Parallel Processing Letters, 9(01): 53-68. 1999.\n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n \n \n \n \n\n\n\n
\n
@article{dinneen1999construction,\n title={Construction of time-relaxed minimal broadcast networks},\n author={Dinneen, Michael J. and Ventura, Jose A. and Wilson, Mark C. and Zakeri, Golbon},\n journal={Parallel Processing Letters},\n volume={9},\n number={01},\n pages={53-68},\n year={1999},\n publisher={World Scientific Publishing Company},\n keywords={algorithms, combinatorics, graphs},\n url_Paper={https://www.worldscientific.com/doi/abs/10.1142/S0129626499000086},\n abstract={In broadcasting, or one-to-all communication, a message originally held\nin one node of the network must be transmitted to all the other nodes. A\nminimal broadcast network is a communication network that can transmit a\nmessage originated at any node to all other nodes of the network in\nminimum time. In this paper, we present a compound method to construct\nsparse, time-relaxed, minimal broadcast networks ( $t$-mbn), in which\nbroadcasting can be accomplished in slightly more than the minimum time.\nThe proposed method generates a new network by connecting a subset of\nnodes from several copies of a $t_1$-mbn using the structure of another\n$t_2$-mbn. The objective is to construct a network as sparse as possible\nsatisfying the desired broadcasting time constraint. Computational\nresults illustrate the effectiveness of the proposed method.}\n}\n\n
\n
\n\n\n
\n In broadcasting, or one-to-all communication, a message originally held in one node of the network must be transmitted to all the other nodes. A minimal broadcast network is a communication network that can transmit a message originated at any node to all other nodes of the network in minimum time. In this paper, we present a compound method to construct sparse, time-relaxed, minimal broadcast networks ( $t$-mbn), in which broadcasting can be accomplished in slightly more than the minimum time. The proposed method generates a new network by connecting a subset of nodes from several copies of a $t_1$-mbn using the structure of another $t_2$-mbn. The objective is to construct a network as sparse as possible satisfying the desired broadcasting time constraint. Computational results illustrate the effectiveness of the proposed method.\n
\n\n\n
\n\n\n
\n
\n\n \n \n Dinneen, M. J.; Ventura, J. A.; Wilson, M. C.; and Zakeri, G.\n\n\n \n \n \n \n \n Compound constructions of broadcast networks.\n \n \n \n \n\n\n \n\n\n\n
Discrete Applied Mathematics, 93(2-3): 205-232. 1999.\n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n \n \n \n \n\n\n\n
\n
@article{dinneen1999compound,\n title={Compound constructions of broadcast networks},\n author={Dinneen, Michael J. and Ventura, Jose A. and Wilson, Mark C. and Zakeri, Golbon},\n journal={Discrete Applied Mathematics},\n volume={93},\n number={2-3},\n pages={205-232},\n year={1999},\n publisher={North-Holland},\n keywords={algorithms, combinatorics, graphs},\n url_Paper={https://www.sciencedirect.com/science/article/pii/S0166218X99000438},\n abstract={Compound methods have been shown to be very effective in the\nconstruction of minimal broadcast networks (mbns). Compound methods\ngenerate a large mbn by combining multiple copies of an mbn $G$ using\nthe structure of another mbn $H$. Node deletion is also allowed in some\nof these methods. The subset of connecting nodes of $G$ has been defined\nas solid $h$-cover by Bermond, Fraigniaud and Peters, and center node\nset by Weng and Ventura. This article shows that the two concepts are\nequivalent. We also provide new properties for center node sets,\nincluding bounds on the minimum size of a center node set, show how to\nreduce the number of center nodes of an mbn generated by a compound\nmethod, and propose an iterative compounding algorithm that generates\nthe sparsest known mbns in many cases.}\n}\n\n
\n
\n\n\n
\n Compound methods have been shown to be very effective in the construction of minimal broadcast networks (mbns). Compound methods generate a large mbn by combining multiple copies of an mbn $G$ using the structure of another mbn $H$. Node deletion is also allowed in some of these methods. The subset of connecting nodes of $G$ has been defined as solid $h$-cover by Bermond, Fraigniaud and Peters, and center node set by Weng and Ventura. This article shows that the two concepts are equivalent. We also provide new properties for center node sets, including bounds on the minimum size of a center node set, show how to reduce the number of center nodes of an mbn generated by a compound method, and propose an iterative compounding algorithm that generates the sparsest known mbns in many cases.\n
\n\n\n
\n\n\n\n\n\n